package Leetcode.每日一题;

/**
 * @ClassName 修车的最少时间
 * @since: 2023/9/7 11:49
 * @auth: kirito
 * @description:
 * 给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
 *
 * 同时给你一个整数 cars ，表示总共需要修理的汽车数目。
 *
 * 请你返回修理所有汽车 最少 需要多少时间。
 *
 * 注意：所有机械工可以同时修理汽车。
 *
 * 示例 1：
 *
 * 输入：ranks = [4,2,3,1], cars = 10
 * 输出：16
 * 解释：
 * - 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
 * - 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
 * - 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
 * - 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
 * 16 分钟是修理完所有车需要的最少时间。
 * 示例 2：
 *
 * 输入：ranks = [5,1,8], cars = 6
 * 输出：16
 * 解释：
 * - 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
 * - 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
 * - 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。
 * 16 分钟时修理完所有车需要的最少时间。
 *
 *
 * 我们发现问题在时间 t 上存在单调性：
 *
 * 假设可以在 t 时间内修完所有车，那么大于 t 的时间都能修完；
 * 如果不能在 t 时间内修完所有车，那么小于 t 的时间都无法修完。
 * 因此，我们可以用二分查找寻找 「可以修完的最小时间」：
 *
 * 二分的下界：1；
 * 二分的上界：将所有的车交给能力值排序最高的工人，因为他的效率最高。
 *
 **/
public class 修车的最少时间 {
    public long repairCars(int[] ranks, int cars) {
        // 初始化左边界为0，右边界为第一个汽车修复所需时间的上限
        long left = 0, right = 1L * ranks[0] * cars * cars;

        // 使用二分查找法在[left, right]的范围内搜索最小的修理时间
        while (left < right) {
            // 计算中间值mid
            long mid = (left + right) >> 1;

            // 统计在修理时间为mid时，可以修复的汽车数量
            long cnt = 0;
            for (int r : ranks) {
                // 计算修理时间mid内，每个等级汽车的修理数量，并求和
                cnt += Math.sqrt(mid / r);
            }

            // 根据统计结果调整边界
            if (cnt >= cars) {
                // 修理的汽车数量大于等于目标数量，缩小右边界
                right = mid;
            } else {
                // 修理的汽车数量小于目标数量，增大左边界
                left = mid + 1;
            }
        }

        // 返回左边界，即为最小的修理时间
        return left;
    }

}
